#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std;

struct Node {
    int x, y;
    int step;
    Node* prev;
};

bool isValid(int x, int y, int n, vector<vector<int>>& matrix) {
    return (x >= 0 && x < n && y >= 0 && y < n && matrix[x][y] == 0);
}

Node* bfs(vector<vector<int>>& matrix, int start_x, int start_y, int end_x, int end_y) {
    int n = matrix.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<Node*> q;
    q.push(new Node{ start_x, start_y, 0, nullptr });
    visited[start_x][start_y] = true;

    static int dx[] = { -1, 0, 1, 0 };
    static int dy[] = { 0, 1, 0, -1 };

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();

        if (current->x == end_x && current->y == end_y) {
            cout << "Minimum number of steps to reach the destination: " << current->step << endl;
            return current;
        }

        for (int i = 0; i < 4; ++i) {
            int new_x = current->x + dx[i];
            int new_y = current->y + dy[i];

            if (isValid(new_x, new_y, n, matrix) && !visited[new_x][new_y]) {
                Node* newNode = new Node{ new_x, new_y, current->step + 1, current };
                q.push(newNode);
                visited[new_x][new_y] = true;
            }
        }
    }

    return nullptr;
}

void generate_maze(vector<vector<int>>& matrix, int start_x, int start_y, int end_x, int end_y) {
    srand(time(0));
    int n = matrix.size();

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((i == start_x && j == start_y) || (i == end_x && j == end_y)) {
                matrix[i][j] = 0;
            }
            else {
                matrix[i][j] = rand() % 2;
            }
        }
    }
}

void display_maze(const vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (const auto& row : matrix) {
        for (int value : row) {
            cout << (value == 1 ? "\033[31m1\033[m" : "\033[32m0\033[m") << " "; // 红色障碍:1，绿色路径:0
        }
        cout << endl;
    }
}

void mark_shortest_path(vector<vector<int>>& matrix, Node* node) {
    while (node->prev) {
        matrix[node->x][node->y] = -1; // 将路径上的点标记为-1
        node = node->prev;
    }
}

void display_maze_with_shortest_path(const vector<vector<int>>& matrix) {
    int n = matrix.size();

    for (const auto& row : matrix) {
        for (int value : row) {
            if (value == 1) {
                cout << "\033[31m1\033[m";
            }
            else if (value == -1) {
                cout << "\033[34m@\033[m"; // 蓝色最优路径:@
            }
            else {
                cout << "\033[32m0\033[m";
            }
            cout << " ";
        }
        cout << endl;
    }
}

void save_to_file(const vector<vector<int>>& matrix) {
    ofstream fout("map.txt");
    for (const auto& row : matrix) {
        for (int value : row) {
            fout << (value == -1 ? 0 : value);
        }
        fout << endl;
    }
    fout.close();
}

int main() {
    int n, start_x, start_y, end_x, end_y;

    cout << "Enter the size of the maze:";
    cin >> n;

    do {
        cout << "Enter the start coordinates (x y):";
        cin >> start_x >> start_y;
        cout << "Enter the end coordinates (x y):";
        cin >> end_x >> end_y;
    } while (start_x == end_x && start_y == end_y);

    vector<vector<int>> matrix(n, vector<int>(n, 0));

    generate_maze(matrix, start_x, start_y, end_x, end_y);

    display_maze(matrix);

    cout << "Finding the shortest path:" << endl;

    Node* shortestPathNode = nullptr;
    while (!(shortestPathNode = bfs(matrix, start_x, start_y, end_x, end_y))) {
        generate_maze(matrix, start_x, start_y, end_x, end_y);
    }

    mark_shortest_path(matrix, shortestPathNode);
    display_maze_with_shortest_path(matrix);

    save_to_file(matrix);

    return 0;
}
